package total;

public class MergeSort {
	
	//自底向上对链表排序
	public void mergeSortBu(int[] arr, int n){
		for(int sz = 1;sz <= n;sz += sz){
			for(int i = 0;i + sz < n;i += sz + sz){
				this.merge(arr, i, i + sz - 1, Math.min(i + sz + sz -1, n - 1));
			}
		}
	}
	
	public void mergeSort(int[] arr,int n){
		this.mergeSort(arr,0,n-1);
	}
	
	private void mergeSort(int[] arr,int l,int r){
		
		if(l >= r)return;
		
//		if( l - r <= 15){
//			insertionSort(arr,l,r);
//			return;
//		}
		
		int mid = (l + r)/2;
		this.mergeSort(arr,l,mid);
		this.mergeSort(arr,mid+1,r);
		if(arr[mid] > arr[mid + 1])
			this.merge(arr,l,mid,r);
	}
	
	private void merge(int[] arr,int l,int mid,int r){
		int[] temp = new int[r - l + 1];
		for(int i = l;i <= r; i++){
			temp[i - l] = arr[i];
		}
		
		int i = l,j = mid + 1;
		
		for(int k = l;k <=r;k ++){
			if(i > mid){
				arr[k] = temp[j - l];
				j++;
			}else if(j > r){
				arr[k] = temp[i - l];
				i++;
			}else if(temp[i - l] < temp[j -l]){
				arr[k] = temp[i-l];
				i ++;
			}else{
				arr[k] = temp[j - l];
				j ++;
			}
		}
	}
	
	public static void main(String[] args) {
		int[] arr = new int[]{2,41,1,1,5,35,26,34,2,34};
		new MergeSort().mergeSort(arr, arr.length);
		for(int a : arr){
			System.out.println(a);
		}
	}
}
